package com.zecan.dynamic;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: lenovo
 * \* Date: 2021/10/11
 * \* Time: 16:58
 * \* Description:
 * \
 */
public class knapsack {
    public static void main(String[] args) {
        int[] val = {0,1500,3000,2000}; // 商品的价值
        int[] w = {0,1,4,3}; // 商品的重量
        int n = 4; // 背包的最大容量
        int m = val.length; // 物品的个数
        int[][] v = new int[m][n+1]; //存储物品的最大价值
        int[][] path = new int[m][n+1];//存储存入商品的下标
        // 动态规划进行分配
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[0].length; j++) {
                if(w[i] > j) { //如果当前添加物品的重量大于当前背包的容量
                    v[i][j] = v[i - 1][j]; //此时存放的就是前一行同个重量的最优策略
                }else{ // 否则 就是 j >= w[i] 背包容量大于等于当前添加商品的重量
                        if(v[i - 1][j] < val[i] + v[i - 1][j - w[i]]) { // 如果上一个的最优解小于当前解
                            path[i][j] = 1; // 记录下标
                            v[i][j] =  val[i] + v[i - 1][j - w[i]]; // 那么就将当前解放入存储最大价值的数组中
                    }
                }
            }
        }
        for(int[] i : v) {
            for(int j : i) {
                System.out.print(j+ " ");
            }
            System.out.println();
        }

        int i = v.length - 1; // 物品的个数
        int j = v[0].length - 1;  //背包的最大容量
        while(i > 0 && j > 0) {
            if(path[i][j] == 1) {
                System.out.println("第" + i + "商品加入");
                j -= w[i]; //此时将 j减去当前商品的重量
            }
            i--;
        }
    }
}
